package twobranchTree.inorderTraversal;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/10
 * @author 王光浩
 * @Description 给出一颗二叉树，使用中序遍历法遍历他。
 * @Thinking 使用栈来解决该问题。将根节点放入栈内即可。
 */
public class MyMethodThree {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
		if (root == null)
			return result;
		TreeNode node = root;
		while (!stack.isEmpty() || node != null) {
			if (node.left != null) { // 左子树存在，且没有加入到栈中
				stack.add(node);
				node = node.left;
			}
			// 左子树不存在，将该节点加入结果集中，取出当前节点的父节点，将父节点加入结果集中
			// 然后判断父节点是否存在右子树，如果存在则将将右子节点赋给node，否则继续从stack中取出数据
			else {
				result.add(node.val);
				// 判断根节点是否存在右子树（不存在的话需要将不断从栈内取出值）
				while (!stack.isEmpty() && node.right == null) {
					node = stack.removeLast();
					result.add(node.val);
				}
				node = node.right;
			}
		}
		return result;
	}
	
	/**
	 * @date 2020/06/06
	 * @param 王光浩 
	 * @return 利用一个栈对二叉树进行中序遍历
	 */
	public List<Integer> inorderTraversal2(TreeNode root) {
		List<Integer> ret = new ArrayList<Integer>();  //保存结果集
		if (root == null)
			return ret;
		Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); //进行中序遍历的容器
		if (root != null)
			stack.push(root);
		while ( !stack.isEmpty() ) {
			TreeNode node = stack.peek();
			if (node.left != null)       //在左子树不为 null 的情况下，将左子节点添加到栈中
				stack.push(node.left);
			else {						 //不断从栈中取出元素，直到取出节点存在右子树，或者栈为 空。
				stack.poll();
				ret.add(node.val);
				while ( !stack.isEmpty() && node.right == null) {
					node = stack.poll();
					ret.add(node.val);
				}
				if (node.right != null)	 //防止由于栈为空，但 node.right为空的情况
					stack.push(node.right);
			}
		}
		return ret;
	}
}
